package com.teng.algorithm.sort;

import java.util.Arrays;

/**
 * @author liangtl
 * @Date 2023/3/5
 * @Return
 * @Description: 希尔排序
 */
public class ShellSort {

    public static void main(String[] args) {
        int[] arr = new int[100000];
        for (int i = 0; i < 100000; i++) {
            arr[i] = (int) (Math.random() * 800000);
        }
        //shellSortChange(arr);
        long l = System.currentTimeMillis();
        System.out.println("开始希尔排序,请耐心等候.....");
        //int[] arrResult = shellSortChange(arr);
        int[] arrResult = shellSortMove(arr);
        System.out.println("排序完成！");
        long l1 = System.currentTimeMillis();
        System.out.println("希尔排序十万个数据总耗时：" + (l1 - l) + "ms");
    }

    //逐步推导
    public static void shellSortChange(int[] arr) {
        int temp;
        // 第一轮排序，10个元素分为5组
        for (int i = 5; i < arr.length; i++) {
            for (int j = i-5; j >=0; j-=5) {
                //如果当前元素大于步长+5后的元素，则交换位置
                if ( arr[j] > arr[j+5]) {
                    temp = arr[j];
                    arr[j] = arr[j+5];
                    arr[j+5] = temp;
                }
            }
        }
        System.out.println("第一轮排序结果为： " + Arrays.toString(arr));

        // 第一轮排序，10个元素分为5%2 = 2组
        for (int i = 2; i < arr.length; i++) {
            for (int j = i-2; j >= 0; j-=2) {
                //如果当前元素大于步长+5后的元素，则交换位置
                if ( arr[j] > arr[j+2]) {
                    temp = arr[j];
                    arr[j] = arr[j+2];
                    arr[j+2] = temp;
                }
            }
        }
        System.out.println("第二轮排序结果为： " + Arrays.toString(arr));

        // 第一轮排序，10个元素分为5%2 = 2组
        for (int i = 1; i < arr.length; i++) {
            for (int j = i-1; j >= 0; j-=1) {
                //如果当前元素大于步长+5后的元素，则交换位置
                if ( arr[j] > arr[j+1]) {
                    temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                }
            }
        }
        System.out.println("第三轮排序结果为： " + Arrays.toString(arr));

        // 希尔排序 交换式
        for (int gap = arr.length/2; gap > 0; gap /= 2) {
            for (int i = gap; i < arr.length; i++) {
                for (int j = i-gap; j >= 0; j-=gap) {
                    //如果当前元素大于步长+5后的元素，则交换位置
                    if ( arr[j] > arr[j+gap]) {
                        temp = arr[j];
                        arr[j] = arr[j+gap];
                        arr[j+gap] = temp;
                    }
                }
            }
        }
    }
    
    //希尔排序 移动式
    public static int[] shellSortMove(int[] arr) {
        int value = 0;
        int index = 0;
        // 固定步长
        for (int gap = arr.length / 2; gap >= 1; gap /= 2) {
            for (int i = gap; i < arr.length; i++) {
                index = i;
                value = arr[index];
                // 如果满足条件，进行插入排序，注意和前面插入排序的区别点
                if (arr[index] < arr[index-gap]) {
                    while (index - gap >= 0 && value < arr[index - gap]) {
                        arr[index] = arr[index - gap];
                        index -= gap;
                    }
                    // 找到位置，插入
                    arr[index] = value;
                }
            }
        }
        return arr;
    }
}
